public class Plane {
	private Seat[] seats;
	private int size;
/**
 * Plane constructor	
 * @param size
 */
	public Plane(int size){
		seats = new Seat[size];
		this.size=size;
		for(int i=0; i < size; i++)
			seats[i] = new Seat();
	}
/**
 * 
 * @param id
 * @return generate a ticket from the id using a hash func.
 */
	private int ticket(int id){ // h(k) hash for finding a seat.
		int ticket = (int)((id/Math.sqrt(5))%size);
		return ticket;
	}
	/**
	 * 
	 * @param id
	 * @return how many steps where needed to seat the passenger
	 */
	public int findseat(int id){ // use hash to put passenger in the plane
		int ticket = ticket(id);
		int steps = walk(ticket , id);
		//for testing System.out.println(+steps);
		return steps;
	}
/**
 * 		
 * @param ticket
 * @param id
 * @return how many steps it took
 */
	private int walk(int ticket, int id){
		if(this.seats[ticket].isavail()){
			seats[ticket].modifyseat();
			return 0;
		}
		int i = 1;
		int steps = 0;
		boolean seated = false;
		boolean up = (ticket==size-1);
		boolean down = (ticket==0);
		while (true){
			if((ticket+i)==size-1){
				up = true;
				steps++;
				if(this.seats[ticket+i].isavail()){
					seats[ticket+i].modifyseat();
					return steps;
				}	
			}
			if((ticket-i)==0){
				down = true;
				steps++;
				if(this.seats[ticket-i].isavail()){
					seats[ticket-i].modifyseat();
					return steps;
				}
			}
			if(!up){
				steps++;
				if(this.seats[ticket+i].isavail()){
					seats[ticket+i].modifyseat();
					return steps;
				}
			}
			if(!down){
				steps++;
				if(this.seats[ticket-i].isavail()){
					seats[ticket-i].modifyseat();
					return steps;
				}
			}	
			i++;
		}
	}
}
